package gameplaying;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class SGFunction {

	
	//以HDU1848 Fibonacci again and again
	//求得每个子游戏的SG值，然后再逐个异或，求出结果
	public static void main(String[] args) {
		SGFunction object = new SGFunction();
//		object.getRes();
//		object.getResII();
		object.getResIII();
	}
	
	// Runtime : 390MS
	public void getRes(){
		initFibonacci();
		initSG();
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int m = scanner.nextInt();
			int n = scanner.nextInt();
			int p = scanner.nextInt();
			if(m == 0 && n == 0 && p == 0){
				break;
			}
			//组合游戏的SG值等于所有子游戏的SG值得异或和
			int sum = sg[m] ^ sg[n] ^ sg[p];
			if(sum == 0){
				System.out.println("Nacci");
			}else{
				System.out.println("Fibo");
			}
		}
		scanner.close();
	}
	
	public static final int SIZE = 16; 
	public static final int MAX = 1002;
	int[] fibonacci = new int[SIZE];
	int[] sg = new int[MAX];
	
	public void initFibonacci(){
		fibonacci[0] = 1;
		fibonacci[1] = 2;
		for(int i = 2; i < SIZE; i++){
			fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]; 
//			System.out.print(fibonacci[i] + " ");
		}
//		System.out.println();
	}
	
	//接下来动态规划求sg的函数值
	public void initSG(){
		sg[0] = 0;
		sg[1] = 1;
		for(int i = 2; i < MAX; i++){
			HashSet<Integer> set = new HashSet<>();
			for(int j = 0; j < SIZE; j++){
				if(fibonacci[j] > i){
					//注意虽然对于这个可以，但是不要这样写，因为如果所有的集合数都小于i，那么会导致不计算sg[i]的值
//					sg[i] = mex(set); 
					break;
				}
				set.add(sg[i - fibonacci[j]]);
			}
			sg[i] = mex(set); 
		}
//		for(int i = 0; i < 100; i++){
//			System.out.print(sg[i] + " ");
//			if(i % 20 == 0){
//				System.out.println();
//			}
//		}
	}
	
	//求最小不包含非负整数
	public int mex(HashSet<Integer> set){
		int i = 0;
		while(set.contains(i)){
			i++;
		}
		return i;
	}
	
	
	//S-Nim HDU1536  
	public static final int MAX_STONES = 10002;
	int[] sNimSG = new int[MAX_STONES];
	
	//set表示能够取的范围值
	public void initSNimSG(int[] set, int n){
		sNimSG[0] = 0;
		for(int i = 1; i < MAX_STONES; i++){
			HashSet<Integer> nextSet = new HashSet<>();
			for(int j = 0; j < n; j++){
				if(set[j] > i){
					//这样写就错了
//					sNimSG[i] = mex(nextSet);
					break;
				}
				nextSet.add(sNimSG[i - set[j]]);
			}
			//之前将这句写在if里面的，因为如果所有的集合数都小于i那sg[i]得不到更新。
			sNimSG[i] = mex(nextSet);
		}
	}
	
	public static final int SETSIZE  = 102;
	int[] set = new int[SETSIZE];
	
	public int[] stones = new int[MAX_STONES];
	
	// Runtime：1747MS
	public void getResII(){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int size = scanner.nextInt();
			if(size == 0){
				break;
			}
			for(int i = 0; i < size; i++){
				set[i] = scanner.nextInt(); 
			}
			Arrays.sort(set, 0, size);
			//初始化SG函数值
			initSNimSG(set, size);
			int testCase = scanner.nextInt();
			for(int t = 1; t <= testCase; t++){
				int  n = scanner.nextInt();
				for(int i = 0; i < n; i++){
					stones[i] = scanner.nextInt(); 
				}
				int sum = 0;
				for(int i = 0; i < n; i++){
					sum ^= sNimSG[stones[i]];
				}
				if(sum == 0){
					System.out.print("L");
				}else{
					System.out.print("W");
				}
			}
			System.out.println();
		}
		scanner.close();
	}
	
	
	public static final int MAX_COUNT = 1002;
	public static final int SET_LENGTH = 102;
	
	int[] stoneSG = new int[MAX_COUNT];
	int[] stoneSet = new int[SET_LENGTH];
	public int curSetLength;
	
	//HDU 2999, 只能取连续的集合S中的石子数
	//超时了
	private int getSG(int n){
		//比如5,只能取2个石子的话，那么就只能留下(1, 3), {(1), (4, 5)}, {(1, 2), (5)}, (3, 5)
		//我们只需要对每个进行异或，然后mex操作即可
		if(stoneSG[n] != -1){
			return stoneSG[n];
		}
		HashSet<Integer> nextSet = new HashSet<>();
		for(int i = 0; i < curSetLength; i++){
			if(stoneSet[i] > n){
				break;
			}
			//遍历所有可能的解
			//比如五个而言，分别计算左边有0个，1个，2个，3个的情况
			for(int j = 0; j <= n - stoneSet[i]; j++){
				if (stoneSG[j] == -1){
					stoneSG[j] = getSG(j);
				}
				if(stoneSG[n - j - stoneSet[i]] == -1){
					stoneSG[n - j - stoneSet[i]] = getSG(n - j - stoneSet[i]);
				}
				nextSet.add(stoneSG[j] ^ stoneSG[n - j - stoneSet[i]]);
			}
		}
		stoneSG[n] = mex(nextSet);
		return stoneSG[n];
	}
	
	public void getResIII(){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			curSetLength = scanner.nextInt();
			for (int i = 0; i < curSetLength; i++) {
				stoneSet[i] = scanner.nextInt();
			}
			//由于stoneSet里面可能有重复的，我们要去重
			Arrays.sort(stoneSet, 0, curSetLength);
			
			int tempLength = 0;
			for(int i = 1; i < curSetLength; i++){
				if(stoneSet[i] != stoneSet[tempLength]){
					stoneSet[++tempLength] = stoneSet[i];
				}
			}
			curSetLength = tempLength + 1;
			int group = scanner.nextInt();
//			while(group-- > 0){
//				int n = scanner.nextInt();
//				if(stoneSG[n] == -1){  
//					stoneSG[n]= getSG(n);
//				}
//				if(stoneSG[n] != 0){
//	                System.out.println("1");
//				}else{  
//	                System.out.println("2");
//				}
//			}
			initSGIII();
			while(group-- > 0){
				int n = scanner.nextInt();
				if(stoneSG[n] != 0){
	                System.out.println("1");
				}else{  
	                System.out.println("2");
				}
			}
		}
		scanner.close();
	}
	
	//Runtime: 655MS
	public void initSGIII(){
		boolean[] temp = new boolean[1001];
		stoneSG[0] = 0;
		for(int i = 1; i < MAX_COUNT; i++){
			Arrays.fill(temp, false);
			for (int j = 0; j < curSetLength; j++) {
				if (stoneSet[j] > i) {
					break;
				}
				temp[stoneSG[i - stoneSet[j]]] = true; // 取边上的
				if (i - stoneSet[j] > 1) {
					int tot = i - stoneSet[j];
					for (int k = 1; k < tot; k++) {
						// 枚举断开位置，变成两堆石子
						temp[stoneSG[k] ^ stoneSG[tot - k]] = true;
					}
				}
			}
			int j = 0;
			while (temp[j]){
				j++;
			}
			stoneSG[i] = j;
		}
	}
}
